package com.company.Algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class MediumMain {
    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }

    // 46.全排列
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {

        }
        return list;
    }

    // 15.三数之和
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        int sum = 0;
        Arrays.sort(nums);
        int start = 0, index = 0, end = 0;
        while (start < nums.length - 2) {
            if (start > 1 && nums[start] == nums[start - 1]) {
                start++;
                continue;
            } else {
                index = start + 1;
                end = nums.length - 1;
                while (index < end) {
                    sum = nums[start] + nums[index] + nums[end];
                    if (sum == 0) {
                        List<Integer> array = new ArrayList<>();
                        array.add(nums[start]);
                        array.add(nums[index]);
                        array.add(nums[end]);
                        list.add(array);
                        index++;
                    } else if (sum > 0) {
                        end--;
                    } else {
                        index++;
                    }
                }
            }
            start++;
        }
        return list;
    }

    // 11.盛水最多的容器
    public static int maxArea(int[] height) {
        int max = Integer.MIN_VALUE;
        // 1-暴力破解
        // for (int i = 0; i < height.length - 1; i++) {
        // for (int j = i + 1; j < height.length; j++) {
        // int h = Math.min(height[i], height[j]);
        // int w = j - i;
        // max = Math.max(h * w, max);
        // }
        // }
        // 2-滑动窗口
        int start = 0, end = height.length - 1;
        while (end - start > 0) {
            int w = end - start;

            if (height[start] > height[end]) {
                max = Math.max(height[start] * w, max);
                end--;
            } else {
                max = Math.max(height[end] * w, max);
                start++;
            }
        }
        return max;
    }

    // 3.无重复字符的最长子串
    public static int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        int max = 0;
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            Character ch = s.charAt(i);
            if (hashMap.containsKey(ch)) {
                max = Math.max(max, i - index);
                index = Math.max(hashMap.get(ch) + 1, index);
            }
            hashMap.put(ch, i);
        }
        max = Math.max(max, s.length() - index);
        return max;
    }
}
